package leetcode.doublepoint;

/**
 * 
 * @author 26233
 *
 *
 *给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: "aba"
输出: True
示例 2:

输入: "abca"
输出: True
解释: 你可以删除c字符。
注意:

字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-palindrome-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode680_ValidPalindrome {
	
	public static boolean validPalindrome(String s) {
		int p = 0, q = s.length() - 1;
		while(p < q) {
			
			if(s.charAt(p) == s.charAt(q)) {
				p++;
				q--;
			}else {// 不相等时至少会发生一次修改
				int s1 = p, s2 = q;
				boolean flag1 = true, flag2 = true;
				q--;
				// 检查删除一个字符后，剩下的字符串是否符合回文串规则
				while(p < q) {
					if(s.charAt(p) == s.charAt(q)) {
						p++;
						q--;
					}else {
						flag1 = false;
						break;
					}
				}
				s1++;
				while(s1 < s2) {
					if(s.charAt(s1) == s.charAt(s2)) {
						s1++;
						s2--;
					}else {
						flag2 = false;
						break;
					}
				}
				// 如果只有一个flag=false，说明有一种删除情况是符合要求的。如果都为false,说明至少还会发生一次删除
				return !(flag1 == false && flag2 == false);
			}
		}
		return true;
    }
	
	public static void main(String[] args) {
		System.out.println(validPalindrome("abc"));
	}

}
